package com.xsherl.leetcode.solution;

public class XORDecode {

    /*
     * 因为是小于等于n的数，且不会重复，即所有数字在[1,n]中且不重复
     * 设n=5
       则perm=[a,b,c,d,e]
           enco=[f,g,h,i]
       因为n确定，所以可以知道所有数的异或结果
       即a^b^c^d^e的结果是知道的
     * 我们知道的是enco的值，只需要找到perm的随意一个位置的值就可以构造答案
     * 可以发现
       f=a^b
       g=b^c
       h=c^d
       i=d^e
     * 现在知道a^b^c^d^e，可以用g=b^c和i=d^e去消除，只剩下一个a，这样perm就构造出来一个元素，即答案
     */
    public int[] decode(int[] encoded) {
        int len = encoded.length;
        int[] perm = new int[len + 1];
        int x = 1;
        for (int i = 1; i <= len; ++i) {
            x ^= i + 1;
        }
        for (int i = 1; i < len; i += 2) {
            x ^= encoded[i];
        }
        perm[0] = x;
        for (int i = 1; i < perm.length; ++i) {
            perm[i] = perm[i - 1] ^ encoded[i - 1];
        }
        return perm;
    }

}
